<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
           最长递增子序列：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
           子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
           子序列。
           输入：nums = [10,9,2,5,3,7,101,18]
           输出：4
           解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
        */
        /* 
            时间：O(n ^ 2)
            空间：O(n)
        */
        var lengthOfLIS = function(nums) {
            let result = 1;
            const dp = new Array(nums.length).fill(1);
            for (let i = 1; i < nums.length; i++) {
                for (let j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1)
                    }
                }
                result = Math.max(result, dp[i])
            }
            console.log(dp, 'dp');
            
            return result
        };
        console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));
        console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));
    </script>
</body>

</html>